package 剑指专题.二叉树;


/*
 * Author：江松
 * Date：2023/3/25 16:39
 *
 在二叉树中找到两个节点的最近公共祖先
 1,从根分别遍历，路径最后一个相同点就是公共祖先
 */

import java.util.ArrayList;

public class Main13 {

    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }



    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        if(root==null)return -1;
        if(root.val==o1||root.val==o2)return root.val;
        //搜索左右子树的公共祖先
        int left=lowestCommonAncestor(root.left,o1,o2);
        int right=lowestCommonAncestor(root.right,o1,o2);
        //左子树没找到,则在右子树中
        if(left==-1)return right;
        //右子树没找到,则在左子树中
        if(right==-1)return left;
        //当前节点
        return root.val;
    }
}
